<head>
    <meta charset="UTF-8">
<title>算法训练 The Year of Code Jam</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】<br />
热情的选手Sphinny正在看新一年的日程表，并发现已经安排了很多编程竞赛。她将这一年的每一天都用以下三种方式之一在日程表上打标记。<br />
1.  白色：这一天她将不参加竞赛。或许这一天没有预定的竞赛，或许			这一天有更重要的事情要做（生活中肯定还有其他美好的事情）。<br />
2.  蓝色：这一天她将参加一场竞赛。<br />
3.  问号：这一天有预定好的竞赛，但她还没有决定好是否参加。<br />
为了简化问题，我们假设没有资格的概念：你不必参加一场比赛去取得另一场比赛的参赛资格。<br />
Sphinny生活的世界与我们的世界有所不同，那个世界里一年有n个月，每个月恰有m天。<br />
下面的图片是一张5个月，每个月有8天的日程表。上面有15天标记为蓝色，5天标记了问号。<br />
<img src="http://lx.lanqiao.cn/RequireFile.do?fid=FaAme8Lf" width="303" height="207" alt="" /><br />
看她美丽的日程表。Sphinny认为对于每一天，有四天与它相邻（可能有的不存在）：同一个月的前一天，同一个月的后一天，前一个月的同一天，后一个月的同一天。<br />
Sphinny想最大化所有竞赛的喜悦值之和。一场竞赛的喜悦值的计算方式是：<br />
1.  初始为4。<br />
2.  每有与那一天相邻的一天要参赛，喜悦值减1。（你可以认为Sphinny喜欢竞赛，但连续参赛让她感觉很累。并且出于审美的原因，在相邻两个月的同一天参赛也不是很好。）<br />
现在，Sphinny想计划这一年，并决定把每一个问号标记都改为白色标记或蓝色标记。她的目标很简单，就是最大化总喜悦值。<br />
下图是上面例子的一种解决方案。通过把2个问号标记变为蓝色标记，剩下的3个问号标记变为白色标记，她可以得到喜悦值42。<br />
<img src="http://lx.lanqiao.cn/RequireFile.do?fid=65BtnBer" width="303" height="211" alt="" /><br />
【输入格式】<br />
第一行一个整数T表示测试数据组数。<br />
对于每一组数据：第一行两个整数n，m表示有n个月，每个月有m天。之后n行每行一个长度为m的字符串，第i行第j个字符表示第i个月的第j天的状态，&ldquo;#&rdquo;表示这一天被标记为蓝色，&ldquo;.&rdquo;表示这一天被标记为白色，&ldquo;?&rdquo;表示这一天被标记为问号。<br />
【输出格式】<br />
对于每一组数据，输出：<br />
Case #X: Y<br />
X是第几组测试数据，Y是最大总喜悦值。<br />
【样例输入】<br />
2<br />
3 3<br />
.?.<br />
.?.<br />
.#.<br />
5 8<br />
.#...##.<br />
.##..?..<br />
.###.#.#<br />
??#..?..<br />
###?#...<br />
【样例输出】<br />
Case #1: 8<br />
Case #2: 42<br />
【数据规模和约定】<br />
对于10%的数据     n，m&le;5<br />
对于30%的数据     n，m&le;15<br />
另20%的数据       m&le;10<br />
另20%的数据       T=1<br />
对于100%的数据     n，m&le;50 ； T&le;100</p>